简单问题复杂化是解决问题的一个好方法。
令 ci 表示 i 出现的次数,n 为最大数字。
i=1∑nj=1∑nci×cj×lcm(i,j)
i=1∑nj=1∑nci×cj×gcd(i,j)i×j
k=1∑ni=1∑nj=1∑n[gcd(i,j)=k]ci×cj×ki×j
k=1∑ni=1∑⌊kn⌋j=1∑⌊kn⌋[gcd(i,j)=1]cik×cjk×i×j×k
k=1∑ni=1∑⌊kn⌋j=1∑⌊kn⌋d∣gcd(i,j)∑μ(d)×cik×cjk×i×j×k
k=1∑nd=1∑⌊kn⌋μ(d)×d2i=1∑⌊kdn⌋j=1∑⌊kdn⌋cikd×cjkd×i×j×k
k=1∑nkd=1∑nμ(d)×d2i=1∑⌊kdn⌋j=1∑⌊kdn⌋cikd×cjkd×i×j×k
T=1∑nT(d∣T∑μ(d)×d)i=1∑⌊Tn⌋j=1∑⌊Tn⌋ciT×cjT×i×j
T=1∑nT(d∣T∑μ(d)×d)(i=1∑⌊Tn⌋ciT×i)2
第一个括号预处理,第二个括号直接暴力算。
预处理和查询复杂度均为 Θ(nlnn)。
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 5e4;
int n , m , k , cnt[ MAXN + 5 ] , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
long long Ans , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
mu[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
mu[ i ] = -1;
}
for( int j = 1 ; j <= k && i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
for( int i = 1 ; i <= MAXN ; i ++ )
for( int j = i ; j <= MAXN ; j += i )
f[ j ] += i * mu[ i ];
}
int main( ) {
sieve( );
scanf("%d",&n);
for( int i = 1 , x ; i <= n ; i ++ )
scanf("%d",&x) , cnt[ x ] ++ , m = max( m , x );
n = m;
for( int i = 1 ; i <= n ; i ++ ) {
long long tmp = 0;
for( int j = 1 ; j <= n / i ; j ++ )
tmp += 1ll * cnt[ i * j ] * j;
Ans += i * f[ i ] * tmp * tmp;
}
printf("%lld", Ans );
return 0;
}